package cn.com.mdx.sort.heapsort.priorityqueue;

import cn.com.mdx.sort.SortUtils;

import java.util.Random;

/**
 * <p> 二叉堆实现优先队列
 *
 * @author ：huangy
 * @date ：Created in 2020/10/14 5:19 下午
 */
@SuppressWarnings(value = {"unchecked"})
public class BinaryHeapMaxPQ<Key extends Comparable<Key>> {

    private final Random random = new Random();

    /**
     * 点集
     */
    private final Key[] pq;

    /**
     * 容器容量
     */
    private int N;

    public BinaryHeapMaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity];
    }

    /**
     * @param key 数据
     * @return void
     * @Author huangy
     * @description //TODO 向二叉堆中插入数据
     * @date 9:44 上午 2020/10/16
     **/
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }

    /**
     * @param index 要上浮的节点位置
     * @return void
     * @Author huangy
     * @description //TODO 节点上浮
     * @date 9:45 上午 2020/10/16
     **/
    public void swim(int index) {
        while (index > 1 && SortUtils.less(pq[index / 2], pq[index])) {
            SortUtils.exChange(pq, index, index / 2);
            index = index / 2;
        }
    }

    /**
     * @return max 最大节点
     * @Author huangy
     * @description //TODO 删除最大节点
     * @date 10:18 上午 2020/10/16
     **/
    public Key delMax() {
        //获取最大节点
        Key max = pq[1];
        //最大节点和最小节点交换
        SortUtils.exChange(pq, 1, N--);
        //节点下沉
        sink(1);
        pq[N + 1] = null;
        return max;
    }

    /**
     * @param index 要下沉的节点位置
     * @return void
     * @Author huangy
     * @description //TODO 节点下沉
     * @date 10:19 上午 2020/10/16
     **/
    public void sink(int index) {
        while (2 * index <= N) {
            //节点index扩大两倍(子节点位置)
            int j = 2 * index;
            if (j < N && SortUtils.less(pq[j], pq[j + 1])) j = j + 1;
            if (!SortUtils.less(pq[index], pq[j])) break;
            SortUtils.exChange(pq, index, j);
            index = j;
        }
    }

    /**
     * @return Key 最大节点
     * @Author huangy
     * @description //TODO 获取最大节点
     * @date 10:35 上午 2020/10/16
     **/
    public Key max() {
        if (!isEmpty()) return pq[1];
        return null;
    }

    /**
     * @return boolean true 表示为空 false 表示不为空
     * @Author huangy
     * @description //TODO 判断容器是否为空
     * @date 10:38 上午 2020/10/16
     **/
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * @return void
     * @Author huangy
     * @description //TODO 打印数组
     * @date 10:41 上午 2020/10/16
     **/
    private void printArray() {
        if (!isEmpty()) {
            for (int i = 1; i <= N; i++) {
                if (i != N) System.out.print(pq[i] + "|");
                else System.out.println(pq[i]);
            }
        }
    }

    /**
     * @return Key 随机样本
     * @Author huangy
     * @description //TODO 从优先队列中获取随机样本
     * @date 3:41 下午 2020/10/26
     **/
    public Key sample() {
        //获取随机数 1 - N之间(既包括1也包括N)
        int randomNum = random.nextInt(N) + 1;
        return pq[randomNum];
    }

    /**
     * @return Key 随机样本
     * @Author huangy
     * @description //TODO 从优先队列中随机删除样本
     * @date 3:42 下午 2020/10/26
     **/
    public Key delRandom() {
        int randomNum = random.nextInt(N) + 1;
        Key randomKey = pq[randomNum];
        //将要删除的元素与队列末尾元素交换
        SortUtils.exChange(pq, randomNum, N);
        pq[N--] = null;
        return randomKey;
    }

    public static void main(String[] args) {
        int N = 16;
        Random random = new Random();
        BinaryHeapMaxPQ<Integer> binaryHeapMaxPQ = new BinaryHeapMaxPQ<>(N + 1);
        //向容器中插入数据
        for (int i = 0; i < N; i++) {
            binaryHeapMaxPQ.insert(random.nextInt(N));
            //binaryHeapMaxPQ.printArray();
        }
        //从容器中取出数据
//        for (int i = 0; i < N; i++) {
//            System.out.println(binaryHeapMaxPQ.delMax());
//            binaryHeapMaxPQ.printArray();
//        }
        for(int i = 0; i < N; i++) {
            binaryHeapMaxPQ.printArray();
            System.out.println(binaryHeapMaxPQ.delRandom());
        }

    }

}
